package com.moyoutian.leetcode;

import com.moyoutian.utils.ArrayUtils;

/**
 * 334. 递增的三元子序列
 * <p>
 * <p>
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * <p>
 * <p>
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：nums = [1,2,3,4,5]
 * <p>
 * 输出：true
 * <p>
 * 解释：任何 i < j < k 的三元组都满足题意
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：nums = [5,4,3,2,1]
 * <p>
 * 输出：false
 * <p>
 * 解释：不存在满足题意的三元组
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * <p>
 * 输入：nums = [2,1,5,0,4,6]
 * <p>
 * 输出：true
 * <p>
 * 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 1 <= nums.length <= 5 * 105
 * <p>
 * -231 <= nums[i] <= 231 - 1
 * <p>
 * <p>
 * 进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
 */
public class Demo334 {

    /**
     * 估计9:30开始
     * 10:02AC
     *
     * @param args
     */
    public static void main(String[] args) {
//        int[] nums = {1, 2, 3, 4, 5};
//        int[] nums = {5, 4, 3, 2, 1};
        int[] nums = {1, 5, 0, 4, 1, 3};
        System.out.println(Solution.increasingTriplet(nums));
        for (int i = 0; i < 100000; i++) {
            nums = ArrayUtils.getIntAr();
            if (Solution.increasingTriplet(nums) != Solution.increasingTripletBL(nums)) {
                ArrayUtils.printArray(nums);
            }
        }
    }


    static class Solution {
        public static boolean increasingTriplet(int[] nums) {
            //记录当前数组前面便利的最小值
            int minI = Integer.MAX_VALUE;
            //记录 满足任意二元组的最小值，i<j ,num<num[j]的num[j]的最小值。
            int minJ = Integer.MAX_VALUE;
            //便利数组
            for (int i = 0; i < nums.length; i++) {
                minI = Math.min(minI, nums[i]);
                if (nums[i] > minJ) {//满足算元组的条件
                    return true;
                } else if (nums[i] > minI) {//满足二元组的条件
                    minJ = Math.min(minJ, nums[i]);
                }

            }
            return false;
        }

        public static boolean increasingTripletBL(int[] nums) {
            //便利数组
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    for (int k = j + 1; k < nums.length; k++) {
                        if (nums[i] < nums[j] && nums[j] < nums[k]) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }
}
